Computer graphics are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, entertainment, and most recently, the home, are tapping into the enormous and rapidly growing list of applications developed for today's increasingly powerful computer devices. Graphical user interfaces have replaced textual interfaces as the standard means for user computer interaction and 3 dimensional (3D) graphics applications are widely used to visually present graphic objects to the user.
In a 3D computer generated image, objects are typically described by data models. These models store descriptions of graphics "primitives" (e.g., polygons, lines, points, etc.) that define the shape of the object, the object attributes, and the connectivity and positioning of how the objects fit together. The polygons connect at common edges defined in terms of common vertices and enclosed volumes. The polygons are textured, Z-buffered, and shaded/illustrated onto an array of pixels, creating a realistic 3D image. Until recently, real time user interaction with 3D models and pseudo-realistic images was generally performed on very high performance workstations. These workstations contain dedicated, special purpose graphics hardware, and are typically very expensive. The progress of semiconductor fabrication technology has made it possible to do real time 3D animation, with color shaded images of complex objects, described by thousands of polygons, on relatively inexpensive rendering subsystems.
Referring now to prior art FIG. 1, a diagram 100 of a polygon 101 from a 3D object is shown. Polygon 101 is one of a number of polygons comprising a 3D object (not shown) and is oriented in 3D space as shown by the x, y, and z axis. Polygon 101 is a triangle polygon defined by three vertices a, b, and c. Each of the vertices a, b, and c are located in 3D space by their respective x, y, and z coordinates. Polygon 101 is stored in a computer readable memory by storing the attributes of each defining vertex a, b, and c. As is well known in the art, each vertex includes, in addition to the x, y, and z coordinates, "argb" (transparency, red, green, blue), "s" (specular highlight), "w" (perspective), and "u" and "v" (texel coordinates). Hence, each of vertices a, b, and c typically includes eight pieces of information, x, y, z, a, w, u, and v. Each of these pieces of information are stored as a 32 bit data word in the memory of a computer system.
Polygon 101 is rendered by a special 3D graphics rendering pipeline implemented on the computer system. The graphics rendering pipeline includes dedicated, special purpose graphics hardware (e.g., integrated circuits optimized for geometry transformation, specialized graphics rendering integrated circuits, and the like) to speed the rendering process. For efficiency, the logic comprising these integrated circuits is implemented in fast integrated circuit hardware. This hardware is optimized to process the vertices comprising a polygon from "top to bottom." Thus, prior to passing the vertices a, b, and c to the graphics pipeline, they are sorted based upon their respective y attributes such that polygon 101 is passed to the graphics rendering pipeline as vertex c, vertex a, and vertex b. In this manner, rendering of an object proceeds from top to bottom.
There are generally two widely used methods of sorting polygon vertices. The first method is software based sorting. In software based sorting, the vertices a, b, and c are stored in a memory of a computer system in an arbitrary order (e.g., typically the order in which the vertices a, b, and c were defined by a 3D graphics application). The vertices a, b, and c are subsequently sorted through software based indirect addressing using a sorted address map. The address map points to the vertices a, b, and c in such a manner that they are sorted from top to bottom (e.g., c, a, b). References to the vertices a, b, and c are thus actually references to the pointers of the sorted address map.
Software based sorting, however, is very inefficient. As described above, each reference to a data word of a vertex (e.g., vertex a) is actually a reference to the sorted address map. Each reference requires that a pointer to the data word be fetched prior to fetching the data word itself. Thus, references to any of vertices a, b, or c would consume at least two clock cycles as opposed to one.
The second method of sorting polygon vertices is called physical location based sorting. In physical location based sorting, the vertices a, b, and c are initially stored in the memory of the computer system in an arbitrary order, as described above. The vertices a, b, and c are subsequently sorted by physically swapping the vertices among locations in the memory. Hence, in the case of vertices a, b, and c, if the vertices are initially stored in the order of a, b, and c, vertex c and vertex b are physically swapped such that the order becomes c, a, b. Each subsequent reference to a data word of the vertex (e.g., vertex a) consumes only one clock cycle.
Physical location based sorting, however, requires the movement of large amounts of data. For example, to swap vertex b and c, vertex b is transferred to a temporary memory location, vertex c is transferred to the memory location previously occupied by vertex b, and vertex b is transferred from the temporary memory location to the memory location previously occupied by vertex c. As described above, each of vertices a, b, and c includes 8 attributes and consumes a total of 8 data words. Hence, swapping vertex b and c consumes 24 clock cycles. Where a 3D object contains a large number of vertices, statistics dictate on average approximately 20 clock cycles per triangle polygon are consumed swapping vertices (e.g., a percentage of these triangle polygons are in the correct order initially).
Thus, what is required is a graphics display system which sorts the vertices of polygons with respect to a polygon attribute which allows references to the vertices to occur in one clock cycle. What is needed is a solution that does not consume a large number of clock cycles sorting vertices through physically moving them around in memory. Additionally, what is needed is a solution that interfaces seamlessly with existing specialized graphics rendering integrated circuits and enhances the efficiency of the graphics rendering process. The present invention provides such an advantageous solution.